package com.itheima.leetcode.od.b.violentenumeration;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

/**
 * (A卷,100分)- 猜数字（Java & JS & Python）
 * <p>
 * 题目描述
 * <p>
 * 一个人设定一组四码的数字作为谜底，另一方猜。
 * <p>
 * 每猜一个数，出数者就要根据这个数字给出提示，提示以XAYB形式呈现，直到猜中位置。
 * <p>
 * 其中X表示位置正确的数的个数（数字正确且位置正确），而Y表示数字正确而位置不对的数的个数。
 * <p>
 * 例如，当谜底为8123，而猜谜者猜1052时，出题者必须提示0A2B。
 * <p>
 * 例如，当谜底为5637，而猜谜者才4931时，出题者必须提示1A0B。
 * <p>
 * 当前已知N组猜谜者猜的数字与提示，如果答案确定，请输出答案，不确定则输出NA。
 * <p>
 * 输入描述
 * <p>
 * 第一行输入一个正整数，0＜N ＜ 100。
 * <p>
 * 接下来N行，每一行包含一个猜测的数字与提示结果。
 * <p>
 * 输出描述
 * <p>
 * 输出最后的答案，答案不确定则输出NA。
 * <p>
 * 用例
 * <p>
 * 输入	6
 * <p>
 * 4815 1A1B
 * <p>
 * 5716 0A1B
 * <p>
 * 7842 0A1B
 * <p>
 * 4901 0A0B
 * <p>
 * 8585 3A0B
 * <p>
 * 8555 2A1B
 * <p>
 * 输出	3585
 * 说明	无
 */
public class BullsAndCows {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        infos = new String[n][2];
        for (int i = 0; i < n; i++) {
            infos[i][0] = sc.next();
            infos[i][1] = sc.next();
        }*/

        String input = "4815 1A1B\n5716 0A1B\n7842 0A1B\n4901 0A0B\n8585 3A0B\n8555 2A1B";
        infos = Arrays.stream(input.split("\n"))
                .map(s -> s.split(" "))
                .toArray(String[][]::new);

        System.out.println(getResult());
    }

    static String[][] infos;

    public static String getResult() {
        ArrayList<HashSet<Character>> num = getCombine();
        ArrayList<String> cache = new ArrayList<>();

        for (Character c1 : num.get(0)) {
            for (Character c2 : num.get(1)) {
                for (Character c3 : num.get(2)) {
                    for (Character c4 : num.get(3)) {
                        String answer = new String(new char[]{c1, c2, c3, c4});
                        if (isValid(answer)) {
                            cache.add(answer);
                        }
                    }
                }
            }
        }

        // 答案不确定则输出NA
        if (cache.size() != 1) {
            return "NA";
        } else {
            return cache.get(0);
        }
    }

    // 剪枝逻辑，本题的后期优化主要在这个方法内进行
    // 返回的是一个集合，集合有四个元素，分别对应四码的谜底数字的每一位，而每个集合元素又是一个Set，里面存放谜底数字对应的位上可能是哪些数字
    public static ArrayList<HashSet<Character>> getCombine() {
        List<Character> tmp = Arrays.asList('0', '1', '2', '3', '4', '5', '6', '7', '8', '9');
        ArrayList<HashSet<Character>> num = new ArrayList<>();
        // 初始时，四码谜底的每一位都有十种可能，即每一位都能取值0~9
        for (int i = 0; i < 4; i++) {
            num.add(new HashSet<>(tmp));
        }

        // 将infos按照猜测提示进行字典序升序，即0A0B排在最前面，4A0B排在最后面，这样排序的用意是0A0B可以不依赖其他条件完成数字过滤
        //    Arrays.sort(infos, (a, b) -> a[1].compareTo(b[1]));

        // 遍历猜谜者猜的数字guess_num与提示guess_result
        for (String[] info : infos) {
            String guess_num = info[0];
            String guess_result = info[1];

            // 数字正确且位置正确的个数
            int countA = guess_result.charAt(0) - '0';
            // 数字正确而位置不对的数的个数
            int countB = guess_result.charAt(2) - '0';

            // 如果countA == 0,则说明当前guess_num的每一位上的数字的位置都不正确，即对应位上不应该出现对应数字
            if (countA == 0) {
                for (int i = 0; i < 4; i++) {
                    Character c = guess_num.charAt(i);
                    if (countB == 0) {
                        // 如果countB == 0，则说明当前guess_num上所有位上的数字都不正确，即任意位上都不应该出现该数字
                        num.get(0).remove(c);
                        num.get(1).remove(c);
                        num.get(2).remove(c);
                        num.get(3).remove(c);
                    } else {
                        num.get(i).remove(c);
                    }
                }
            }
        }

        return num;
    }

    // 判断谜底answer是否正确，即是否符合所有猜测提示
    public static boolean isValid(String answer) {
        for (String[] info : infos) {
            String guess = info[0];
            String expect_result = info[1];
            String real_result = getGuessResult(guess, answer);
            if (!expect_result.equals(real_result)) {
                return false;
            }
        }
        return true;
    }

    // 获取猜的数字guess在指定谜底answer下的猜测提示
    public static String getGuessResult(String guess, String answer) {
        int countA = 0;
        int countB = 0;

        int[] answer_arr = new int[10];
        int[] guess_arr = new int[10];

        for (int i = 0; i < guess.length(); i++) {
            char c1 = guess.charAt(i);
            char c2 = answer.charAt(i);

            if (c1 == c2) {
                countA++;
            } else {
                answer_arr[c2 - '0']++;
                guess_arr[c1 - '0']++;
            }
        }

        for (int i = 0; i < 10; i++) {
            countB += Math.min(answer_arr[i], guess_arr[i]);
        }

        return new StringBuilder().append(countA).append("A").append(countB).append("B").toString();
    }
}